package com.gxc.array;

/**
 * 给定一个整型矩阵，返回子矩阵的最大累计和
 *
 * 解法：
 * 根据多行相加变成一维数组后，可再根据TopScore计算
 * 题目变成
 * 按行枚举所有的行结果（0-0,0-1,0-n, 1-1,1-n.......n-n）
 * 然后行相加变成一维数组，求出最大的累计和
 */
public class ChildTopScore {

    public static void main(String[] args) {
        int size = 1000;
        for (int i = 0; i < size; i++) {
            int[][] arr = random();
            if (childTopScore(arr)!=childTopScore2(arr)) {
                printArr(arr);
                System.out.println("算法错误");
                break;
            }
        }

        int[][] testArr = new int[][]{{35, -49, 29, -55, -10, -7 },
                                    {-44, -38, -50, -55, -78, 5 }};
        System.out.println(childTopScore(testArr));
        System.out.println(childTopScore2(testArr));
    }

    public static int childTopScore(int[][] arr) {
        int max = Integer.MIN_VALUE;
        for (int row = 0; row < arr.length; row++) {
            for (int row2 = row; row2 < arr.length; row2++) {
                int[] mergeRow = merge(arr, row, row2);
                int score = TopScore.process(mergeRow);
                max = Math.max(max, score);
            }
        }

        return max;
    }

    /**
     * 行合并
     * @param arr
     * @param cur 当前行
     * @param tar 目标行
     * @return
     */
    private static int[] merge(int[][] arr, int cur, int tar) {
        int[] result = new int[arr[0].length];
        for (int row = cur; row <= tar; row++) {
            for (int col = 0; col < result.length; col++) {
                result[col] += arr[row][col];
            }
        }
        return result;
    }

    public static int childTopScore2(int[][] arr) {
        int max = Integer.MIN_VALUE;
        for (int row = 0; row < arr.length; row++) {
            int[] result = new int[arr[0].length];
            for (int row2 = row; row2 < arr.length; row2++) {
                int cur = 0;
                for (int col = 0; col < result.length; col++) {
                    result[col] += arr[row2][col];
                    cur += result[col];
                    max = Math.max(cur, max);
                    cur = cur<0?0:cur;
                }
            }
        }

        return max;
    }

    private static int[][] random() {
        int row = (int) (Math.random()*10+1);
        int col = (int) (Math.random()*10+1);
        int[][] arr = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[i][j] = (int) (Math.random()*50-Math.random()*100);
            }
        }
        return arr;
    }

    private static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println("");
        }
    }
}
